package com.LeetCode.BackTrace;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 全排列
 */
public class Permution {

    public List<List<Integer>> permute(int[] nums) {
        ArrayList<Integer> list = new ArrayList<>();
        for(int num : nums){
            list.add(num);
        }
        int n = nums.length;
        dfs(0, list, n);
        return res;
    }

    List<List<Integer>> res = new ArrayList<>();

    /**
     *
     * @param index 层数
     * @param list 存放结果
     * @param n 长度
     */
    public void dfs(int index, ArrayList<Integer> list, int n){
        if(index == n){
            res.add(new ArrayList<>(list));
        }

        for(int i = index; i<n; i++){
            Collections.swap(list, index, i);
            dfs(index+1, list, n);
            Collections.swap(list, index, i);
        }
    }

    @Test
    public void test(){
        permute(new int[]{1,2,3}).forEach(System.out::println);
    }
}
